<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 二叉树得存储结构
        class BSTree {
            constructor(data) {
                // 数据域
                this.data = data;
                // 左指针域
                this.left = null;
                // 右指针域
                this.right = null;
                // 存放当前节点数据得对象
                this.root = this;
            }
        }

        // 二叉树得操作方式
        class Tree {
            constructor() {
                // 记录数节点
                this.root = null
            }

            // 添加二叉树
            // data: 需要添加得参数
            // 1. 创建节点。2.找一个合适得位置 插入节点

            // insert(data) {
            //     // 创建节点
            //     const newNode = new BSTree(data)

            //     // 递归 添加节点得函数
            //     const insertNode = (root, newNode) => {
            //         // 判断新节点 是否小于 当前节点root
            //         if (newNode.data < root.data) {
            //             // 如果小于当前节点，就要插入到左指针域，还需要判断左指针域是否存在值，
            //             if (root.left !== null) {
            //                 // 如果存在值 就在递归 判断
            //                 insertNode(root.left, newNode)
            //             } else {
            //                 // 如果不存在 就直接添加
            //                 root.left = newNode
            //             }
            //         } else if (newNode.data > root.data) {
            //             // 如果新节点 大于 当前节点，将新节点保存到右指针域，还需要判断右指针域 是否有值
            //             if (root.right !== null) {
            //                 // 如果有值，在递归 判断
            //                 insertNode(root.right, newNode)
            //             } else {
            //                 // 不存在就直接添加
            //                 root.right = newNode
            //             }
            //         }
            //     }

            //     // 找一个合适得位置 插入节点
            //     if (!this.root) {
            //         // 判断  root中是否记录了值，如果没有记录 就将新创建好得节点 添加到root中
            //         this.root = newNode
            //     } else {
            //         // 通过递归得方式  找到一个合适得位置 插入节点
            //         insertNode(this.root, newNode)
            //     }
            // }


            // 查找二叉树
            search(data) {
                // 创建一个查找得方法
                const searchNode = (node, data) => {
                    // 判断二叉数是否为空树
                    if (node === null) return null

                    // 判断数据域和需要查找的参数 是否相同 如果相同 就代表查找成功 返回该树节点
                    if (node.data === data) return node

                    // 如果 当前二叉树的数据域 大于 需要查找的参数 就需要将左指针域和需要查找的数 重新传递给查找的方法 反之 传入右指针域和当前要查找的数
                    return (node.data > data) ? searchNode(node.left, data) : searchNode(node.right, data)

                }

                return searchNode(this.root, data)
            }

            // 获取二叉树得最大值
            getMax() {
                // 创建一个查找最大值得方式
                const maxNode = (node) => {
                    return node ? ((node.right !== null) ? maxNode(node.right) : node) : null
                }

                return maxNode(this.root)
            }

            // 获取二叉树得最小值
            getMin(node) {
                // 创建一个查找最小值得方式
                const minNode = (node) => {
                    return node ? ((node.left !== null) ? minNode(node.left) : node) : null
                }

                return minNode(node || this.root)
            }

            // 删除二叉树得节点
            remove(data) {
                    // 创建一个删除节点的方法
                    const remobeNode = (node, data) => {
                        // 判断二叉树节点是否为空 如果为空直接返回null, 如果二叉树为空数，调用删除无意义判断
                        if (node === null) return null

                        if (node.data === data) {
                            // 删除操作

                            // 当前二叉树 既没有左节点，也没有右节点
                            if (node.left === null && node.right === null) return null;

                            // 如果左指针域数据为空 就返回右指针域
                            if (node.left === null) return node.right;

                            //  如果右指针域数据为空 就返回左指针域
                            if (node.right === null) return node.left;

                            // 如果左右指针域都有数据的话
                            if (node.right !== null && node.left !== null) {
                                // 从右指针域 获取到最小值  赋值给我当前的数据域
                                const _node = this.getMin(node.right);

                                node.data = _node.data;

                                // 重新整理右指针域
                                node.right = remobeNode(node.right, _node.data);

                                // 整理完成之后 返回
                                return node
                            }

                        } else if (node.data > data) {
                            // 通过左指针域 进行删除递归
                            node.left = remobeNode(node.left, data);

                            return node
                        } else {
                            node.right = remobeNode(node.right, data);

                            return node
                        }
                    }


                    // this.root: 需要删除的二叉树， data：需要删除的数据
                    remobeNode(this.root, data)
                }
                // remove(data) {
                //     // 创建一个删除的方式
                //     const removeNode = (node, data) => {
                //         if (node === null) return null;

            //         if (node.data === data) {
            //             if (node.right === null && node.left === null) return null;

            //             if (node.right === null) return node.left;

            //             if (node.left === null) return node.right;

            //             if (node.left !== null && node.right !== null) {
            //                 // 获取右指针域的最小值
            //                 const _node = this.getMin(node.right);

            //                 node.data = _node.data;

            //                 node.right = removeNode(node.right, _node.data);

            //                 return node
            //             }
            //         } else if (node.data > data) {
            //             node.left = removeNode(node.left, data);

            //             return node
            //         } else {
            //             node.right = removeNode(node.right, data);

            //             return node
            //         }

            //     }

            //     removeNode(this.root, data)
            // }

            inOrder() {
                // 前序遍历
                const arr = [];

                // 创建排序的方法
                const orderNode = (node, callback) => {
                    if (node !== null) {
                        arr.push(callback(node.data))

                        orderNode(node.left, callback)

                        orderNode(node.right, callback)
                    }
                }

                const callback = (v) => {
                    return v
                }

                orderNode(this.root, callback)

                return arr
            }
            nextOrder() {
                const arr = [];

                const nextOrderNode = (node, callback) => {
                    if (node !== null) {
                        nextOrderNode(node.left, callback)
                        arr.push(callback(node.data))


                        nextOrderNode(node.right, callback)

                    }
                };

                const callback = v => v;

                nextOrderNode(this.root, callback)

                return arr
            }
        }

        const myTree = new Tree();

        const arr = [3, 5, 7, 2, 1, 4, 10, 18, 15, 17, 11]

        // myTree.insert(9)
        // myTree.insert(10)
        // myTree.insert(8)

        arr.forEach((item) => {
            myTree.insert(item)
        })

        console.log(myTree)

        const tree = {
            data: 8,
            left: {
                data: 7,
                left: null,
                right: null
            },
            right: {
                data: 9,
                left: null,
                right: null
            }
        }
    </script>
</body>

</html>